package alo.p6.work4;

import alo.p6.BinarySearchTreeNode;

/**
 * @ClassName Delete
 * @Description 删除二叉搜索树中的元素
 * @Author Fanxc
 * @DATE 2021/2/15 9:27
 * @Version 1.0
 */
public class Delete {
    BinarySearchTreeNode delete(BinarySearchTreeNode root,int data){
        BinarySearchTreeNode temp;
        if(root==null){
            System.out.println("Element is not in tree");
        }else if (data< root.getData()){
            root.setLeft(delete(root.getLeft(),data));
        }else if (data> root.getData()){
            root.setRight(delete(root.getRight(),data));
        }else {//找到该元素
            //如果删除结点有两个孩子
            if (root.getLeft()!=null&&root.getRight()!=null){
                temp=new FindMax().findMax(root.getLeft());
                //把左子树中的最大值给目标结点，同时删除左子树中的最大值结点（这样变动的比较小）
                root.setData(temp.getData());
                root.setLeft(delete(root.getLeft(),root.getData()));
            }else {//有一个孩子或者没有孩子
                if (root.getLeft()==null){
                    root=root.getRight();
                }
                if (root.getRight()==null){
                    root=root.getLeft();
                }
            }
        }
        return root;
    }
}
